GermanWikipedia - /page/entry.mu

Micron Document

<!DOCTYPE html>

<title>Wurzel (Graphentheorie)</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Wurzel (Graphentheorie)</span></h1>

</header>

</div>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="de" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="de" dir="ltr"><p>Eine <b>Wurzel</b> ist in der <a href="Graphentheorie" title="Graphentheorie">Graphentheorie</a> ein <a href="Knoten_(Graphentheorie)" title="Knoten (Graphentheorie)">Knoten</a> eines <a href="Graph_(Graphentheorie)" title="Graph (Graphentheorie)">Graphen</a>, der besonders ausgezeichnet worden ist. Der Graph mit einer Wurzel wird als <a href="Wurzelgraph" title="Wurzelgraph">Wurzelgraph</a> bezeichnet.<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup>

</p>

<p>Häufige Anwendungen finden Wurzeln bei der <a href="Traversierung" title="Traversierung">Traversierung</a> von Graphen (bspw. mittels <a href="Breitensuche" title="Breitensuche">Breitensuche</a> oder <a href="Tiefensuche" title="Tiefensuche">Tiefensuche</a>). Die Wurzel stellt den Startknoten dar. Das Ergebnis der Graph-Traversierung ist ein <a href="Spannbaum" title="Spannbaum">Spannbaum</a>.

</p><p>Bei <a href="Wurzelbaum" class="mw-redirect" title="Wurzelbaum">Wurzelbäumen</a> ist die jeweilige Wurzel derjenige Knoten, von dem aus alle anderen Knoten im <a href="Baum_(Graphentheorie)" title="Baum (Graphentheorie)">Baum</a> erreichbar sind und der selbst von keinem anderen Knoten aus erreichbar ist. Eine Wurzel ist somit der einzige Knoten in einem Baum, der keinen Vorgänger hat. Zeichnet man einen Baum, so ist die Wurzel immer der oberste Knoten des Baumes. Bäume haben in der <a href="Informatik" title="Informatik">Informatik</a> immer genau eine Wurzel. Zerlegt man den ursprünglichen Baum in mehrere Teilbäume, so haben auch die entsprechenden Teilbäume wieder genau eine bestimmte Wurzel. Verallgemeinert man den Begriff der Wurzel auf allgemeine Graphen, so spricht man auch von <a href="Quelle_(Graphentheorie)" class="mw-redirect" title="Quelle (Graphentheorie)">Quellen</a>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Alternative_Definition">Alternative Definition</h2></div>

<p>Ein Knoten ist eine Wurzel genau dann, wenn gilt:

</p>

<ul><li>Alle weiteren Knoten des Graphen sind von diesem Knoten aus erreichbar.</li>

<li>Der Knoten hat keinen Vorgänger.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Beispiel">Beispiel</h2></div>

<ul><li>Die Wurzel des Beispielbaumes hat die Marke 1.</li>

<li>Die Wurzel des Teilbaumes, der aus den Knoten 5, 9 und 10 besteht, hat die Marke 5.</li>

<li>Die Wurzel des Teilbaumes, der nur aus dem Knoten 12 besteht, hat die Marke 12.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Einzelnachweise">Einzelnachweise</h2></div>

<li id="cite_note-1"><span class="mw-cite-backlink"><a href="#cite_ref-1">↑</a></span> <span class="reference-text">Peter Tittmann: <cite style="font-style:italic">Einführung in die Kombinatorik</cite>. Springer, 2014, ISBN 978-3-642-54588-7, <span style="white-space:nowrap">S.<span style="display:inline-block;width:.2em"> </span>210</span>, <a href="Digital_Object_Identifier" title="Digital Object Identifier">doi</a>:<span class="uri-handle" style="white-space:nowrap"><a rel="nofollow" class="external text" href="https://doi.org/10.1007/978-3-642-54589-4">10.1007/978-3-642-54589-4</a></span>.<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Wurzel+%28Graphentheorie%29&rft.au=Peter+Tittmann&rft.btitle=Einf%C3%BChrung+in+die+Kombinatorik&rft.date=2014&rft.doi=10.1007%2F978-3-642-54589-4&rft.genre=book&rft.isbn=9783642545887&rft.pages=210&rft.pub=Springer" style="display:none"> </span></span>

</li>

</ol></div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2021-04-07" href="https://de.wikipedia.org/wiki/?title=Wurzel_(Graphentheorie)&oldid=210669485">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>